import java.util.*;


public class HamiltonianCycle {
    private int V; // 图中节点的数量
    private int[] path; // 存储路径
    private int[][] graph; // 图的邻接矩阵

    //初始化图
    public HamiltonianCycle(int[][] graph) {
        this.graph = graph;
        this.V = graph.length;
        this.path = new int[V];
        Arrays.fill(path, -1);
    }
    //递归，遍历所有可能的节点顺序
    public void hamiltonian(int[] path, int pos) {
        if (pos == V) {
            // 如果路径长度等于节点数，检查是否存在从最后一个节点到第一个节点的边
            if (graph[path[pos - 1]][path[0]] == 1) {
                printPath(path);
            }
            return;
        }
        for (int v = 1; v < V; v++) {
            if (isValid(v, path, pos)) { // 判断当前节点是否可以添加到路径中
                path[pos] = v;
                hamiltonian(path, pos + 1);
                path[pos] = -1; // 回溯
            }
        }
    }
    //判断当前节点是否可以添加到路径中
    public boolean isValid(int v, int[] path, int pos) {
        if (graph[path[pos - 1]][v] == 0) { // 判断前一个节点和当前节点之间是否有边
            return false;
        }
        for (int i = 0; i < pos; i++) {
            if (path[i] == v) { // 判断当前节点是否已经在路径中
                return false;
            }
        }
        return true;
    }
    //打印路径
    public void printPath(int[] path) {
        for (int vertex : path) {
            System.out.print(vertex + " -> ");
        }
        System.out.println(path[0]); // 输出回路的起点
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 0, 1, 0},
                {1, 0, 1, 1, 1},
                {0, 1, 0, 0, 1},
                {1, 1, 0, 0, 1},
                {0, 1, 1, 1, 0}
        };
        HamiltonianCycle hc = new HamiltonianCycle(graph);
        hc.path[0] = 0; // 从节点0开始搜索
        hc.hamiltonian(hc.path, 1);
    }
}


